# -*- coding: UTF-8 -*-
from typing import List
from leetcode_helper import SolutionBase, TestcaseHelper


class Solution(SolutionBase):
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        if len(nums1) == 0 and len(nums2) > 0:
            return self.get_median_one_array(nums2)
        elif len(nums2) == 0 and len(nums1) > 0:
            return self.get_median_one_array(nums1)
        elif len(nums1) == 0 and len(nums2) == 0:
            return 0.0
        else:
            return self.get_median_value(nums1, nums2)

    def get_median_value(self, nums1: List[int], nums2: List[int]) -> float:
        m = len(nums1)
        n = len(nums2)
        left_index = (m + n + 1) >> 1
        right_index = (m + n + 2) >> 1

        median_left = self.find_kth(nums1, 0, m - 1, nums2, 0, n - 1, left_index)
        if left_index != right_index:
            median_right = self.find_kth(nums1, 0, m - 1, nums2, 0, n - 1, right_index)
            return (median_right + median_left) / 2
        else:
            return median_left

    def find_kth(self, array1: List[int], start1: int, end1: int, array2: List[int], start2: int,
                 end2: int, k_index: int) -> int:
        len1 = end1 - start1 + 1
        len2 = end2 - start2 + 1

        # 总是让短的数组作为array1
        if len1 > len2:
            return self.find_kth(array2, start2, end2, array1, start1, end1, k_index)
        if len1 == 0:
            return array2[start2 + k_index - 1]
        if k_index == 1:
            return min(array1[start1], array2[start2])

        index_1 = start1 + min(len1, k_index >> 1) - 1
        index_2 = start2 + min(len2, k_index >> 1) - 1

        if array1[index_1] > array2[index_2]:
            return self.find_kth(array1, start1, end1, array2, index_2 + 1, end2, k_index - (index_2 - start2 + 1))
        else:
            return self.find_kth(array1, index_1 + 1, end1, array2, start2, end2, k_index - (index_1 - start1 + 1))

        # 取一个数组的中值

    def get_median_one_array(self, array) -> float:
        length = len(array)
        if length % 2 == 0:
            index1 = length >> 1
            index2 = index1 - 1
            return (array[index1] + array[index2]) / 2.0
        else:
            index = (length + 1) >> 1
            return array[index - 1]
    

if __name__ == '__main__':
    solution = Solution()
    testcases = [
        ([1], [], 1.0),
        ([], [1], 1.0),
        ([], [], 0.0),
        ([1, 2], [3, 4], 2.5),
        ([0, 0], [0, 0], 0.0),
        ([1, 1], [1, 1], 1.0),
        ([2, 2], [2, 2, 2], 2.0),
        ([1, 3], [2], 2.0),
        ([0, 0, 0, 0, 0], [-1, 0, 0, 0, 0, 0, 1], 0.0)
    ]

    for case_item in testcases:
        # 获取测试用的case和期待的执行结果
        # TODO: 单独一条的Test case的组成随题目的不同而改变，需要按照题目来修改代码
        input1 = case_item[0]
        input2 = case_item[1]
        expect = case_item[len(case_item) - 1]
        # TODO: 调用对应方法，需要替换具体的方法
        exec_result = solution.findMedianSortedArrays(input1, input2)

        # 判断执行结果，输出提示信息
        check_result = solution.check_result(expect, exec_result)
        TestcaseHelper.print_case(check_result, case_item, exec_result)
